A signal propagation channel of a telecommunications system can cause interference during transmission through the channel. While interference can occur in many types of systems, in a wireless telecommunications system the transmission path typically attenuates and distorts the signal being transmitted in a number of ways. In the transmission path the interference is typically caused by multi-path propagation of the signal, by different types of fading and reflection, and by other signals transmitted through the same transmission path.
To reduce the influence of interference, different encoding methods have been devised to protect signals from interference and to eliminate errors caused by interference. One frequently used encoding method is convolutional encoding. In convolutional encoding the signal to be transmitted, consisting of symbols, is encoded into code words, which are based on the convolution of the symbols to be transmitted with polynomials. The convolutional code is defined by the coding ratio (rate) and coding polynomials. The coding ratio (k/n) defines the number (n) of encoded symbols in relation to the number (k) of symbols to be encoded. The constraint length K of the code refers to the degree of coding polynomials plus one. The convolutional encoder may be regarded as a state machine with 2K−1 states, and is typically implemented by means of shift registers.
A coding method developed from the convolutional coding method is known as a parallel concatenated convolutional coding method, also referred to as a turbo code. One technique to form a turbo coder is to use at least two recursive and systematic convolutional encoders and interleavers. The resulting code includes a systematic part, which directly corresponds to symbols in the coder input, and at least two parity parts, which are the outputs of the parallel convolutional encoders.
A signal which has propagated through a channel is decoded in a receiver. The convolutional code can be both encoded and decoded using a trellis whose nodes (or states) correspond to the states of the encoder used in signal encoding. The paths between nodes that belong to two successive trellis phases of the trellis correspond to allowed state transitions between the encoder states. The code unequivocally attaches to each state transition: the initial and the final state of the transition, the bit being encoded, and the bits of the encoding result.
The purpose of a decoder at a receiver is to derive the original data bits (at the transmitter) from a received code word. In order to perform this function the decoder typically works with metrics. There are two types of metrics used by the decoder: path metrics (also referred to as state metrics) and branch metrics. The path metrics represent the probability that the set of symbols included in the received signal lead to the state corresponding to the node in question. The branch metrics are proportional to the probabilities of transitions between states.
The well-known Viterbi algorithm is often used for decoding a convolutional code. An example of a decoding method that requires more intensive calculation is a MAP (Maximum Aposteriori Probability) algorithm and its variations, e.g., LogMAP algorithm or MaxLogMAP algorithm. The MAP algorithm is also known as a BCJR algorithm (Bahl, Cocke, Jelinik and Raviv). The MAP algorithm and its variations typically provide a considerably better result than the Viterbi algorithm. Furthermore, since the MAP algorithm and its variations are examples of SISO (Soft Input Soft Output) algorithms, they are particularly well suited for iterative decoding, e.g. for decoding a turbo code where a posteriori probabilities can be utilized. In contradistinction to the MAP-based algorithms, the basic Viterbi algorithm is a Hard Output algorithm that must be converted to obtain soft decisions, which increases its calculation complexity. The algorithms obtained through conversion of the Viterbi algorithm are not, however, as effective as MAP-based algorithms.
To estimate a posteriori probabilities, the MAP algorithm and its variations typically require path metrics for each bit to be decoded, both from the beginning of the trellis to its end, and from the end to the beginning, at the bit in question. According to the prior art, the values of the path metrics of all nodes are stored in a memory in each trellis phase in respect to one direction, e.g., forward through the trellis, and the values are calculated for the other direction, e.g., backwards through the trellis.
A sliding window is typically applied to reduce the memory requirement. The sliding window involves calculating and storing either forward or backward path metrics, with respect to a window of a certain constant length, and then reading the stored path metrics in inverse order. This type of operation is described by H. Dawid and H. Meyr: Real-Time Algorithms and VLSI Architectures for Soft Output Map Convolutional Decoding, in 6th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, Toronto, Canada, Volume 1, pp. 193-197, September 1995.
Another solution to reduce use of memory is to use the LogMAP algorithm, instead of the MaxLogMAP algorithm, to invert the original calculation direction of path metrics, which makes the additional memory unnecessary. This approach is described by S. Huettinger, M. Breiling and J. Huber: Memory Efficient Implementation of the BCJR Algorithm, in Proceedings of the 2nd International Symposium on Turbo Codes and Related Topics, Brest, France, 4-7 September 2000.
Described now with reference to FIG. 1A is an embodiment of a conventional wireless telecommunications system 1 having a transmitter 10 and a receiver 20. In the example the transmitter 10 and the receiver 20 communicate via a radio channel 30. The transmitter 10 includes a data source 12, which may be a speech encoder or another conventional data source used in circuit-switched or packet-switched data transmission.
A signal to be transmitted is received from the output of the data source 12 and supplied to a channel encoder 14, which in this case is a convolutional encoder, preferably a turbo encoder. The encoded symbols are supplied to a modulator 16, where the signal is modulated in a prior art manner. The modulated signal is supplied to a radio frequency block 18, where it is amplified and transmitted to the radio path 30 by an antenna 18A. In the radio path 30 the signal is affected by interference and typically by noise as well. The receiver 20 includes an antenna 22A for receiving the signal, which is supplied to a demodulator 24 via a radio frequency block 22. The demodulated signal is supplied to a channel decoder 26, where the signal is decoded for convolutional codes or turbo codes by a method that produces path metrics over a trellis. From the decoder 26 the decoded signal is supplied to a data sink 28, such as audio circuitry or digital message circuitry.
FIG. 1B illustrates a conventional ½-rate convolutional encoder 14, also known as a recursive systematic convolutional encoder. A set of successive encoder states, referred to as a trellis, is naturally related to each convolutional code. The nodes of two successive trellis phases are connected by paths, which are determined by the state transitions allowed by the convolutional code. The convolutional code attaches to the initial and the final state, the bit to be encoded and the bits of the encoding result to each state transition.
An eight-state systematic and recursive encoder for a convolutional code is next described with reference to FIG. 1B and the Table shown in FIG. 1C.
An input bit, which is described in the first column of the Table, enters the input of the encoder 14. The present state of the encoder 14, i.e., the bits from each delay element (DE) 14A, 14B, 14C are illustrated in the second column of the Table (present encoder state). The third column in the Table shows the next state of the encoder 14. The encoder 14 has two outputs: a systematic bit (SD) and a parity bit (P0), which is illustrated in the fifth column of the Table. Thus, the coding result of one state transition of the encoder 14 involves two bits: the systematic bit SD and the parity bit P0. The encoder 14 further includes summing blocks 14D, 14E, 14F and a feedback line 14G for implementing recursion.
In practical embodiments it is advantageous if the initial and final states of the encoder 14 are pre-determined. For this reason encoding usually begins in a certain state and ends in a pre-determined known state. During encoding the shift of the encoder 14 to a pre-determined final state is referred to as termination, and the bits that are encoded during the shift are referred to as termination bits, which are not actual data. The initial state often contains zero bits only, and the termination also shifts the encoder 14 back to the zero state. This is not, however, always necessary, although this mode of operation facilitates the functioning of the corresponding decoder 26.
FIG. 2 illustrates the structure of a conventional turbo encoder 40 that includes two encoders 42, 44 and an interleaver 46. The bits to be encoded are supplied as such to the output of the turbo encoder 40. This component is called the systematic part SD of the code. The bits to be encoded are also supplied as such to the first encoder 42 and the turbo interleaver 46. The interleaved bits are supplied to the second encoder 44. The output bits PA0, PA1 of the first encoder 42 and the output bits PB0, PB1 of the second encoder 46 are referred to as the parity parts of the code, where PA0 and PA1 are the parity of ascending order and PB0 and PB1 are the parity of interleaved order. The ascending order means the address order in which the original data bits enter the first encoder 42. The interleaved order is the order in which the original data bits enter the second encoder 44.
FIG. 3 illustrates the general structure of a conventional turbo decoder 50 in the case of a ⅕ turbo code. The input to the turbo decoder 50 is the systematic part SDk of the code and four parity parts PA0k, PA1k, PB0k, and PB1k. The turbo decoder 50 comprises two decoder units 52 and 54, also referred to herein as a first unit A and a second unit B. The input to the first decoder unit A includes the systematic part SDk and the parity parts PA0k and PA1k of the code. Furthermore, the input to the first decoder unit A includes extrinsic values EVk from a preceding iteration round. The extrinsic values arrive from the output of the second unit B via a deinterleaver 58. The output of the first unit A includes a new extrinsic value EVk, which is supplied as an input to the second unit B via an interleaver 56, and an output A that includes both a soft value SVA,k and a hard decision on each bit. The output A may be supplied to the other parts of the receiver 20, if desired. The input to the second unit B also includes the systematic part SDk of the code, which arrives via the interleaver 56, and the parity parts PB0k and PB1k of the code. Moreover, the input to the second decoder unit B includes extrinsic values EVk from a preceding iteration round. The extrinsic values arrive from the output of the second unit A via an interleaver 56. The output of the second unit B is the new extrinsic value EVk, which is supplied to the first unit A via the deinterleaver 58, and an output B that includes both soft values SVB,n and a hard decision for each bit that is supplied to the other parts of the receiver 20, if desired. In this scheme one turbo round is assumed to include one consecutive decoding by the unit A and the unit B (beginning with either unit). At the beginning of decoding, all extrinsic values can be set to zero.
The trellis processing performed in connection with the MAP algorithm and its variations, e.g., the LogMAP algorithm and the MaxLogMAP algorithm, that is used in the decoder units A and B includes three main steps: i.e., the forward calculation of path metrics, the backward calculation of path metrics, and the combination of the path metrics calculated by the forward and backward techniques for the calculation of a new extrinsic value, a soft decision, and a hard decision for each data bit. The new extrinsic values are supplied as an input parameter signal to the next iteration round, whereas the hard bit decision is made on the basis of the sign of the soft decision. The branch metrics are typically proportional to the logarithms of the transition probabilities.
In practice, the interleaver 56 and the deinterlever 58 are often implemented using a single interleaver, and the serial decoder (decoders 52 and 54) is implemented using a single decoder unit that performs the functions of the decoder A and decoder B in turn. The decoders A and B can also be arranged in parallel. In this case the decoder units A and B are implemented as separate parallel decoders.
At the output of the decoder A, the soft value SVA,k of each original data bit can be written as:SVA,k=SDk+EVB,k,old+EVA,k,new,where EVB,k,old represents extrinsic values calculated by the previous decoder step B, EVA,k,new are new extrinsic values calculated by the present decoder step A, and SDk are systematic data samples. The sign of the soft value SVA,k is a hard decision on a kth received data bit. The corresponding formula for the soft value SVB,n at the output of the decoder B isSVB,n=SD+EVA,n,old+EVB,n,new where EVA,n,old represents extrinsic values calculated by the previous decoder step A, EVB,n,new are new extrinsic values calculated by the present decoder step B, and SDn are systematic data samples. An important difference between the two soft values is an order that is defined by a turbo interleaver: n=kth interleaver index.
Usually it can be determined from the context which soft value formula is being applied and therefore the following simplified formula for the soft value SVm can be used:SVm=SDm+EVm,old+EVm,new where EVm,old represents extrinsic values calculated by the previous decoder step. EVm,new are new extrinsic values calculated by the present decoder step, and SDm are systematic data samples.
The decoding process is iterative and therefore the receiver 20 will typically set an upper limit on the number of iterations (e.g., a maximum of 10 iterations is typically sufficient). In general, the reliability of the output hard decisions increases as the number of iterations increases.
Regardless of the particular algorithm selected for decoding a turbo coded code word, a problem that is encountered with communication systems having flexible data rates is the detection of the existence of a received turbo coded code word in the presence of channel noise. For example, the use of a flexible data rate implies that the receiver does not know if it has received a signal that consists solely of noise, that is, the received signal does not contain a turbo coded code word at all, or if it has received a noisy, but valid, turbo coded code word. As can be appreciated, to ensure proper operation the receiver must be capable of distinguishing between received noise and a received, albeit noisy, turbo coded code word.
As a more specific statement of a current problem, based on the current version of a standard (TS 25.212) a user equipment (UE), such as a mobile cellular telephone, is expected to perform single transport format detection, among other things, for turbo coded channels. In the single transport format mode of transport format detection there are two possibilities: the UE receives noise or it receives a (turbo coded) code word. If the UE fails to detect the reception of only noise, that is, if the UE erroneously assumes that a code word was received, the power control of overall wireless communications system can be adversely affected. This is true because the power control is based on cyclic redundancy check (CRC) bits. When receiving just noise, the CRC check performed by the UE fails and the UE will request more power. However, the UE should not request more power when receiving just noise as erroneous power requests can destabilize system power control. As such, it is important that the UE be able to accurately distinguish between received noise and true (turbo coded) code words. Prior to this invention, this important need was not adequately addressed.